package leetcode;

import java.util.*;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-10-22 16:05
 **/
public class LeetCode20 {



    /**
     * 使用栈的方法
     * @param s
     * @return
     */
    public boolean isValid2(String s) {
        Deque<Character> stack = new LinkedList<>();
        int len = s.length();
        for (int i = 0; i < len; i++) {
            if (s.charAt(i) == '(' || s.charAt(i) == '[' || s.charAt(i) == '{') {
                switch (s.charAt(i)) {
                    case '{': {
                        stack.push('{');
                        break;
                    }
                    case '[': {
                        stack.push('[');
                        break;
                    }
                    case '(': {
                        stack.push('(');
                        break;
                    }
                }
                continue;
            }
            if (stack.isEmpty()) {
                return false;
            }
            switch (stack.peek()) {
                case '{': {
                    if (s.charAt(i) != '}') {
                        return false;
                    }
                    stack.pop();
                    break;
                }
                case '[': {
                    if (s.charAt(i) != ']') {
                        return false;
                    }
                    stack.pop();
                    break;
                }
                case '(': {
                    if (s.charAt(i) != ')') {
                        return false;
                    }
                    stack.pop();
                    break;
                }
            }
        }
        return stack.isEmpty();
    }

    public boolean isValid(String s) {
        int len = s.length();
        //如果字符串s的长度不是2的倍数直接返回false。
        if (len % 2 != 0) {
            return false;
        }
        Deque<Character> stack = new LinkedList<>();
        Map<Character, Character> map = new HashMap<>();
        map.put(']', '[');
        map.put(')', '(');
        map.put('}', '{');
        for (int i = 0; i < len; i++) {
            if (map.containsKey(s.charAt(i))) {
                if (stack.isEmpty() || !stack.peek().equals(map.get(s.charAt(i)))) {
                    return false;
                }
                stack.pop();
            } else {
                stack.push(s.charAt(i));
            }
        }
        return stack.isEmpty();
    }

}
